package week09

// 845. 八数码 AcWing
// https://www.acwing.com/problem/content/847/

import (
	"fmt"
	"strconv"
)

func main() {
	var grid = make([]int, 9)
	for i := range grid {
		var input string
		fmt.Scanf("%s", &input)
		if input == "x" {
			grid[i] = 0
		} else {
			v, _ := strconv.Atoi(input)
			grid[i] = v
		}
	}

	var start = marshal(grid)
	var target = 123456780

	var dist = make(map[int]int)
	dist[start] = 0

	var queue = &BinaryHeap{}
	queue.push(newNode(eval(grid), start))

	var swap = func(grid []int, state, zeroIdx, next int) {
		grid[zeroIdx], grid[next] = grid[next], grid[zeroIdx]
		newState := marshal(grid)
		if v, ok := dist[newState]; !ok || v > dist[state]+1 {
			dist[newState] = dist[state] + 1
			queue.push(newNode(dist[newState]+eval(grid), newState))
		}
		grid[zeroIdx], grid[next] = grid[next], grid[zeroIdx]
	}

	for !queue.empty() {
		state := queue.pop().state
		if state == target {
			fmt.Println(dist[target])
			return
		}

		grid := unmarshal(state)
		zeroIdx := getZeroIndex(grid)
		x, y := index2xy(zeroIdx)
		if x > 0 {
			next := xy2index(x-1, y)
			swap(grid, state, zeroIdx, next)
		}
		if x < 2 {
			next := xy2index(x+1, y)
			swap(grid, state, zeroIdx, next)
		}
		if y > 0 {
			next := xy2index(x, y-1)
			swap(grid, state, zeroIdx, next)
		}
		if y < 2 {
			next := xy2index(x, y+1)
			swap(grid, state, zeroIdx, next)
		}
	}

	fmt.Println(-1)
}

func eval(grid []int) int {
	var res = 0
	for i, num := range grid {
		if num == 0 {
			continue
		}
		x, y := index2xy(i)
		tx, ty := index2xy(num-1)
		res = res + abs(x - tx) + abs(y - ty)
	}
	return res
}

func xy2index(x, y int) int {
	return x * 3 + y
}

func index2xy(index int) (x int, y int) {
	return index / 3, index % 3
}

func getZeroIndex(grid []int) int {
	for i := range grid {
		if grid[i] == 0 {
			return i
		}
	}
	return -1
}

func marshal(grid []int) int {
	var state = 0
	for _, num := range grid {
		state = state * 10 + num
	}
	return state
}

func unmarshal(state int) []int {
	var grid = make([]int, 9)
	for i := 8; i >= 0; i-- {
		grid[i] = state % 10
		state /= 10
	}
	return grid
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}


type Node struct {
	dist int
	state int
}

func newNode(dist, state int) *Node {
	return &Node{dist, state}
}

type BinaryHeap struct {
	list []*Node
}

func (heap *BinaryHeap) push(val *Node) {
	heap.list = append(heap.list, val)
	var cur = len(heap.list)-1
	var parent = (cur - 1) / 2
	for parent >= 0 {
		if heap.list[parent].dist > heap.list[cur].dist {
			heap.list[parent], heap.list[cur] = heap.list[cur], heap.list[parent]
			cur = parent
			parent = (cur - 1) / 2
		} else {
			break
		}
	}
}

func (heap *BinaryHeap) pop() *Node {
	var val = heap.list[0]
	heap.list[0] = heap.list[len(heap.list)-1]
	heap.list = heap.list[:len(heap.list)-1]
	var cur = 0
	var child = cur * 2 + 1
	for child < len(heap.list) {
		var other = cur * 2 + 2
		if other < len(heap.list) && heap.list[other].dist < heap.list[child].dist {
			child = other
		}
		if heap.list[cur].dist > heap.list[child].dist {
			heap.list[cur], heap.list[child] = heap.list[child], heap.list[cur]
			cur = child
			child = cur * 2 + 1
		} else {
			break
		}
	}
	return val
}

func (heap *BinaryHeap) empty() bool {
	return len(heap.list) == 0
}

